package Top_Interview_Questions.Tree;

import Top_Interview_Questions.Tree.Supple.TreeNode;

import java.util.HashMap;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/8 17:43
 * <p>
 * 官方题解的思想写的不错
 *
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--22/
 * 我看的是上面那个题解
 */
public class _0105 {
    
    public static void main(String[] args) {
        _0105 test = new _0105();
//        int[] preorder = new int[]{3,9,6,8,20,15,7};
//        int[] inorder = new int[]{6,9,8,3,15,20,7};
        int[] preorder = new int[]{3,9,6,8,20,15,7};
        int[] inorder = new int[]{6,9,8,3,15,20,7};
        TreeNode root = test.buildTree2(preorder, inorder);
        System.out.println(root);
    }



    /*--------------------------------------基于方法一改进---------------------------------------*/

    /**
     *       3
     *     /  \
     *    9    20
     *  /  \  /  \
     * 6   8 15   7
     */
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        //[0,preorder.length) 左开右闭，所以后面都是统一的
        return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length, map);
    }

    private TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end,
                                     HashMap<Integer, Integer> map) {
        if (p_start == p_end) {
            return null;
        }
        int root_val = preorder[p_start];
        TreeNode root = new TreeNode(root_val);
        int i_root_index = map.get(root_val);
        int leftNum = i_root_index - i_start;

        /*
         * 辅助记忆边界:
         * 从画图你会发现。下面的两个比较复杂的边界。连起来就是
         * [p_start+1,p_end)
         * [i_start,i_root_index) [i_root_index+1,i_end)
         * 两个都少了一个范围，这个范围就是每颗子树的根节点。所以如果边界范围不太好记，可以画图
         * 或者往这方面想
         */
        root.left = buildTreeHelper(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index, map);
        root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end, map);
        return root;
    }

    /*-----------------------------------------------------------------------------------------*/



    /*----------------------------------------方法一--------------------------------------------*/

    /**
     *
     * 前序遍历 preorder = [3,9,6,20,15,7]
     * 中序遍历 inorder = [6,9,3,15,20,7]
     *
     *       3
     *     /  \
     *    9   20
     *  /  \  /  \
     * 6   8 15   7
     *
     * 通过递归确定每一个子树的根节点，不停的把preorder拆分。而inorder，则以拆分的predorder的根节点的索引
     * 为mid也进行拆分。inorder的拆分你可以用二分法来理解
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {
        // preorder 为空，直接返回 null
        if (p_start == p_end) {
            return null;
        }
        int root_val = preorder[p_start];
        TreeNode root = new TreeNode(root_val);
        //在中序遍历中找到根节点的位置
        int i_root_index = 0;
        for (int i = i_start; i < i_end; i++) {
            if (root_val == inorder[i]) {
                i_root_index = i;
                break;
            }
        }
        int leftNum = i_root_index - i_start;
        //递归的构造左子树
        root.left = buildTreeHelper(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index);
        //递归的构造右子树
        root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end);
        return root;
    }

    /*-----------------------------------------------------------------------------------------*/


}
